home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / cool / ge_cool.lha / GE_COOL2.1 / src / Stack / Stack.C < prev    next >
C/C++ Source or Header  |  1992-06-29  |  10KB  |  301 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12.  
  13. #include <cool/Stack.h>
  14.  
  15. // CoolStack<Type> () -- Empty constructor for the CoolStack class
  16. // Input:            None
  17. // Output:           None
  18.  
  19. template<class Type>
  20. CoolStack<Type>::CoolStack<Type> () {
  21.   this->data = NULL;                // Initialize data
  22.   if (!this->compare_s)
  23.     this->compare_s = &Type##_CoolStack_is_data_equal;
  24. }
  25.  
  26.  
  27. // CoolStack<Type> (long) -- constructor that specifies number of elements
  28. // Input:                Integer number of elements
  29. // Output:               None
  30.  
  31. template<class Type>
  32. CoolStack<Type>::CoolStack<Type> (unsigned long n)
  33. #ifdef __cplusplus
  34.  : CoolStack(n)
  35. #else
  36.  : (n)
  37. #endif 
  38. {
  39.   this->data =  new Type[n];            // Allocate memory
  40.   if (!this->compare_s)
  41.     this->compare_s = &Type##_CoolStack_is_data_equal;
  42. }
  43.  
  44.  
  45. // CoolStack<Type> (void*, long) -- constructor that specifies static-sized storage
  46. //                              and number of elements
  47. // Input:                       Integer number of elements
  48. // Output:                      None
  49.  
  50. template<class Type>
  51. CoolStack<Type>::CoolStack<Type> (void* s, unsigned long n)
  52. #ifdef __cplusplus
  53.  : CoolStack(n)
  54. #else
  55.  : (n) 
  56. #endif 
  57. {
  58.   this->data = (Type*) s;            // Pointer to storage block
  59.   this->alloc_size_s = INVALID;            // Indicate static-size object
  60.   if (!this->compare_s)
  61.     this->compare_s = &Type##_CoolStack_is_data_equal;
  62. }
  63.  
  64.  
  65. // CoolStack<Type> (CoolStack<Type>&) -- constructor for reference to another stack
  66. // Input:                        CoolStack reference
  67. // Output:                       None
  68.  
  69. template<class Type>
  70. CoolStack<Type>::CoolStack<Type> (const CoolStack<Type>& s)
  71. #ifdef __cplusplus
  72.  : CoolStack(s)
  73. #else
  74.  : (s)
  75. #endif
  76. {
  77.   this->data =  new Type[s.size];        // New memory allocation
  78.   for (long i = 0; i < s.number_elements; i++)    // For each element
  79.     this->data[i] = s.data[i];            // Copy data into this
  80. }
  81.  
  82.  
  83. // ~CoolStack<Type> -- Destructor for CoolStack class that frees up storage
  84. // Input:          None
  85. // Output:         None
  86.  
  87. template<class Type>
  88. CoolStack<Type>::~CoolStack<Type> () {
  89.   if (this->size != 0 &&            
  90.       this->alloc_size_s != INVALID)        // If not user-provided storage
  91.     delete [] this->data;            // Free up the memory
  92. }
  93.  
  94.  
  95. // Boolean push(Type&) -- Push item on top of this stack
  96. // Input:                 Reference to a Type value to push onto stack
  97. // Output:                TRUE or FALSE
  98.  
  99. template<class Type>
  100. Boolean CoolStack<Type>::push (const Type& value) {
  101.   if (this->number_elements == this->size) {    // If not enough memory
  102.     if (!this->grow(this->size+1)) return FALSE; // Report failure
  103.   }
  104.   this->data[number_elements++] = value;    // Top item becomes value
  105.   return TRUE;                    // Report success
  106. }
  107.  
  108.  
  109. // Boolean pushn(Type&, long) -- Push n items with a fill value onto this stack
  110. // Input:  Reference to Type value, integer number of items to be pushed
  111. // Output: TRUE or FALSE
  112.  
  113. template<class Type>
  114. Boolean CoolStack<Type>::pushn (const Type& value, long n) {
  115.   if (n < 0)                    // Range-checking error
  116.     return FALSE;                // Return FALSE
  117.   if (n == 0) {                    // For push(foo, 0)
  118.     this->data[number_elements-1] = value;    // Replace top item
  119.     return TRUE;                // Return success
  120.   }
  121.   if (n == 1)                    // If just push one item
  122.     return (push(value));            // Push one item == push
  123.   if (this->number_elements+n > this->size) {    // If not enough memory
  124.     if (!this->grow(this->size+1)) return FALSE; // Report failure
  125.   }
  126.   this->number_elements += n;            // Add n to number of elements
  127.   for (long i = number_elements - n; i < number_elements; i++) // For "n" elts
  128.     this->data[i] = value;                // Fill with value
  129.   return TRUE;                    // Report success  
  130. }
  131.  
  132.  
  133. // Type& popn(long) -- Pop n items off this stack, from the top; return the
  134. //                     nth item
  135. // Input:              Integer number of items
  136. // Output:             nth element of stack
  137.  
  138. template<class Type>
  139. Type& CoolStack<Type>::popn (long n) {
  140. #if ERROR_CHECKING
  141.   if (n < 0)                    // If index out of range
  142.     this->popn_error (#Type, n);        // Raise exception
  143. #endif
  144.   if (n == 0)                    // If top element
  145.     return (this->data[number_elements-1]);    // Return top item
  146.   if (n > this->number_elements)  {        // If arg n > # elements
  147. //     this->number_elements = 0;        // Reset # of elements
  148.     return this->data[0];            // Return last element
  149.   } 
  150.   return (this->data[this->number_elements -= n]); // Return nth from "top"
  151. }
  152.  
  153.  
  154. // CoolStack<Type>& operator= (CoolStack<Type>&) -- Assigns this stack to another stack
  155. // Input:  Reference to a stack
  156. // Output: Reference to modified this
  157.  
  158. template<class Type>
  159. CoolStack<Type>& CoolStack<Type>::operator= (const CoolStack<Type>& s) {
  160.   if (this != &s) {
  161.     if (this->size < s.size) {            // If not enough memory
  162. #if ERROR_CHECKING
  163.       if (this->alloc_size_s == INVALID)    // If static size queue
  164.     this->assign_error (#Type);        // Raise exception
  165. #endif
  166.       if (this->size != 0)
  167.     delete [] this->data;                    // Free it up
  168.       this->data = new Type[s.size];        // Allocate bigger memory
  169.       this->size = s.size;            // New stack size
  170.     }
  171.     this->CoolStack::operator= (s);        // Call base class assignment
  172.     for (long i = 0; i < s.number_elements; i++) // For each element
  173.       this->data[i] = s.data[i];         // Copy value
  174.   }
  175.   return *this;                // Return reference
  176. }
  177.  
  178.  
  179. // Boolean operator== (CoolStack<Type>&) -- Compare this stack with another
  180. //                                      stack; return TRUE if they are equal
  181. // Input:  Reference to a stack
  182. // Output: TRUE or FALSE
  183.  
  184. template<class Type>
  185. Boolean CoolStack<Type>::operator== (const CoolStack<Type>& s) const {
  186.   if (this->number_elements != s.number_elements) // If not same number
  187.     return FALSE;                  // Then not equal
  188.   for (long i = 0; i < this->number_elements; i++) // For each element
  189.     if (!(*this->compare_s)(this->data[i],s.data[i])) // If not equal
  190.       return FALSE;                      // Return failure
  191.   return TRUE;                          // Return sucess
  192. }
  193.  
  194. // Boolean is_data_equal -- Default data comparison function if user has not
  195. //                          provided another one.
  196. // Input:                   Two Type references
  197. // Output:                  TRUE or FALSE
  198.  
  199. template<class Type> CoolStack {
  200.   Boolean Type##_CoolStack_is_data_equal (const Type& t1, const Type& t2) {
  201.     return (t1 == t2);
  202.   }
  203. }
  204.  
  205. // void set_compare(Type##_CoolStack_Compare) -- Set this stack's compare function
  206. // Input:                                    Pointer to a compare function
  207. // Output:                                   None
  208.  
  209. template<class Type>
  210. void CoolStack<Type>::set_compare (Type##_CoolStack_Compare cf) {
  211.   if (cf)
  212.     this->compare_s = cf;            // Set to user function
  213.   else
  214.     this->compare_s = &Type##_CoolStack_is_data_equal; // or set to default
  215. }
  216.  
  217.  
  218. // Boolean find (Type&) -- Return TRUE if value is found in this stack
  219. // Input:                  Reference to a Type value
  220.   // Output:                 TRUE or FALSE
  221.  
  222. template<class Type>
  223. Boolean CoolStack<Type>::find (const Type& value) {
  224.   return this->position(value) >= 0;
  225. }
  226.  
  227.  
  228. // long position (Type&) -- Return the index (from top) of value if found;
  229. //                          otherwise return -1
  230. // Input:                   Reference to a Type value
  231. // Output:                  Integer index or -1
  232.  
  233. template<class Type>
  234. long CoolStack<Type>::position (const Type& value) const {
  235.   for (long i = this->number_elements - 1; i >= 0;  i--) // Search from "top"
  236.     if ((*(this->compare_s))(this->data[i], value))     // If found
  237.       return (this->number_elements-i-1);         // Index from "top"
  238.   return -1;                         // Failure
  239. }
  240.  
  241. // grow -- grow stack on push overflow
  242. // Input:    None
  243. // Output:   None
  244.  
  245. template<class Type>
  246. Boolean CoolStack<Type>::grow (long min_size) {
  247.   if (this->alloc_size_s == INVALID) {        // If not allowed to grow
  248. #if ERROR_CHECKING
  249.     this->push_error (#Type);            // Raise exception
  250. #endif
  251.   return FALSE;                    // Report failure
  252.   }
  253.   if (this->growth_ratio != 0.0 &&
  254.       (this->size * (1.0+growth_ratio)) >= min_size)
  255.     min_size = (long)(this->size * (1.0 + growth_ratio)); // New size
  256.   else
  257.     min_size += alloc_size_s;
  258.   resize(min_size);
  259.   return TRUE;
  260. }
  261.  
  262. // resize -- Adjust the memory size of a CoolStack to accomodate some size
  263. // Input:    Number of elements to hold
  264. // Output:   None
  265.  
  266. template<class Type>
  267. void CoolStack<Type>::resize (long new_size) {
  268.   if (new_size <= this->size) {        // Don't bother shrinking stack
  269. #if ERROR_CHECKING
  270.     if (new_size < 0)                // If index out of range
  271.       this->resize_error (#Type, new_size);    // Raise exception
  272. #endif
  273.     return;
  274.   }
  275.   Type* temp =  new Type[new_size];        // Allocate storage
  276.   for (long i = 0; i < this->number_elements; i++) // For each element in Vector
  277.     temp[i] = this->data[i];               // Copy into new storage
  278.   if (this->size != 0)
  279.     delete [] this->data;            // Free up old memory
  280.   this->data = temp;            // Assign new memory block
  281.   this->size = new_size;        // Save new size value
  282. }
  283.  
  284. // operator<< -- Overload the output operator for CoolStack
  285.       // Input:        ostream reference, stack reference
  286. // Output:       Stack data is output to ostream
  287.  
  288. template<class Type> CoolStack {
  289. ostream& operator<< (ostream& os, const CoolStack<Type>& s) {
  290.   if (s.length() == 0)                // If no elements
  291.     os << " Empty ";                // Report empty status
  292.   else {
  293.     os << "[ ";                    // From top of stack
  294.     for (long i = s.length() - 1; i >= 0; i--)    // For each element
  295.       os << s.data[i] << " ";            // Print data items
  296.     os << "]";                    // Bottom of stack
  297.   }
  298.   return os;                    // Return stream reference
  299. }
  300. }
  301.